package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         1049,
		Discription: "两块石头可抵消为一块重量为差值的石头，给一堆石头碰撞后最后剩的重量",
		Level:       2,
		Labels: map[string]int{
			"0-1背包": 1,
			"动态规划":  1,
			"滚动数组":  1,
			"空间降维":  1,
		},
	})
}

//为什么可以转化为0-1背包：最后的结果可以表示为若干个石头重量取负、其它石头取正的和（>=0），取负的石头总能被取正的石头消耗掉
func LastStoneWeightII(stones []int) int {
	n := len(stones)
	sum := 0
	for i := range stones {
		sum += stones[i]
	}

	target := sum / 2
	//dp[i][j]表示stones[:i]中的石头中是否能取出部分石头，使其重量等于j
	dp := make([][]bool, n+1)
	for i := range dp {
		dp[i] = make([]bool, target+1)
		dp[i][0] = true
	}

	for i := 1; i <= n; i++ {
		for j := 1; j <= target; j++ {
			if stones[i-1] == j {
				dp[i][j] = true
			} else if stones[i-1] > j {
				dp[i][j] = dp[i-1][j]
			} else {
				dp[i][j] = dp[i-1][j] || dp[i-1][j-stones[i-1]]
			}
		}
	}

	//从sum/2开始递减，找第一个能凑成重量的值
	for i := target; i >= 0; i-- {
		if dp[n][i] {
			return sum - 2*i
		}
	}

	return sum
}

//利用滚动数组去掉一维
//dp[i][j]的状态只与dp[i-1][j]有关，正向遍历会更小的j的位置会被提前覆盖，所以从后向前遍历即可
func LastStoneWeightII2(stones []int) int {
	n := len(stones)
	sum := 0
	for i := range stones {
		sum += stones[i]
	}

	target := sum / 2
	dp := make([]bool, target+1)
	dp[0] = true

	for i := 1; i <= n; i++ {
		for j := target; j >= 1; j-- {
			if stones[i-1] == j {
				dp[j] = true
			} else if stones[i-1] < j {
				dp[j] = dp[j] || dp[j-stones[i-1]]
			}
		}
	}

	for i := target; i >= 0; i-- {
		if dp[i] {
			return sum - 2*i
		}
	}

	return sum
}
